import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 216. 组合总和 III
 * <a href="https://leetcode.cn/problems/combination-sum-iii/">...</a>
 * User: DELL
 * Date: 2023-07-22
 * Time: 22:24
 */
public class Solution {
    List<List<Integer>> ans = new ArrayList<>();

    /**
     * 解题思路: (dfs)
     * 本题的关键在于数字是1到9,且每个数字只能使用一次,因此结果集是可以列举的,(通过看
     * 答案,答案基本上全部都是利用各种方法在穷举满足的条件),同时因为最终要的是满足要求
     * 的集合,因此更加笃定得一一列举.因此在这里是利用dfs来遍历所有情况,然后找出符合要
     * 求的结果集,放入 res 中返回即可.同时dfs在遍历的过程中,我们的想法是在1到9这9个
     * 数字中,选择出 k 个数字,让这些数字的和为 n
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        int[] arr = new int[9];
        for(int i = 0; i < 9; i++){
            arr[i] = i + 1;
        }
        dfs(0,n,0,k,arr,new ArrayList<Integer>());
        return ans;
    }

    /**
     * @param sum       当前已选择数字的和
     * @param n         目标数字总和
     * @param index     当前遍历的数字下标
     * @param k         目标数字数量
     * @param arr       记录数字的数组
     * @param list      暂存已选择的数字
     */
    public void dfs(int sum, int n,int index, int k, int[] arr, List<Integer> list){
        if(list.size() == k){
            if(sum == n){
                ans.add(new ArrayList<>(list));
            }
            return;
        }
        for(int i = index; i < arr.length; i++){
            if(arr[i] + sum > n){
                return ;
            }
            list.add(arr[i]);
            sum += arr[i];
            dfs(sum, n, i + 1, k, arr, list);
            sum -= arr[i];
            list.remove(list.size() - 1);
        }
    }
}